//https://www.nowcoder.com/practice/947f6eb80d944a84850b0538bf0ec3a5?tpId=13&&tqId=11179&rp=1&ru=/activity/oj&qru=/ta/coding-interviews/question-ranking


/*
struct TreeNode {
	int val;
	struct TreeNode *left;
	struct TreeNode *right;
	TreeNode(int x) :
			val(x), left(NULL), right(NULL) {
	}
};*/
class Solution {
public:
	void Inorderconvert(TreeNode* cur, TreeNode*& prev)//中序遍历
	{
		if(cur == nullptr)
		{
			return;
		}
		Inorderconvert(cur->left, prev);
		cur->left = prev;
		if(prev)
		{
			prev->right = cur;
		}
		prev = cur;
		Inorderconvert(cur->right, prev);
	}
    TreeNode* Convert(TreeNode* pRootOfTree) 
	{
        TreeNode* prev = nullptr;
		Inorderconvert(pRootOfTree, prev);
		TreeNode* head = pRootOfTree;
		while(head->left && head)
		{
			head = head->left;
		}
		return head;
    }
};
